package com.ljy.my_study.lintcode.翻转链表;

import java.util.ArrayList;
import java.util.List;

/** 
* @author James
* @date 2018年9月28日 
*/
public class TestMain {
//	描述
//	翻转一个链表
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
//
//	挑战
//	在原地一次翻转完成
	public static void main(String[] args) {
		int[] nums= {1,2,3,4,5};
		ListNode head=createListNode(nums);
		System.out.println(head);
		ListNode head2=reverse(head);
		System.out.println(head2);
	}
	
	private static ListNode createListNode(int[] nums) {
		ListNode head=null;
		ListNode nowNode=null;
		for(int i=0;i<nums.length-1;i++) {
			if(i==0) {
				nowNode=new ListNode(nums[i]);
				head=nowNode;
			}
			nowNode.next=new ListNode(nums[i+1]);
			nowNode=nowNode.next;
		}
		return head;
	}
	
	public static ListNode reverse(ListNode head) {
		if(head==null||head.next==null) return head;
		ListNode lastNode=head;
		ListNode nowNode=null;
		ListNode nextNode=null;
		if(head!=null&&head.next!=null)nowNode=head.next;
		if(nowNode!=null&&nowNode.next!=null)nextNode=nowNode.next;
		lastNode.next=null;
		while(nowNode!=null) {
			nowNode.next=lastNode;
			if(nextNode!=null) {
				lastNode=nowNode;
				nowNode=nextNode;
				nextNode=nowNode.next;
			}else {
				break;
			}
		}
		return nowNode;
	}

	public static ListNode reverse2(ListNode head) {
		if(head==null) {
			return null;
		}
		List<ListNode> list=new ArrayList<>();
		ListNode nowNode=head;
		int index=0;
		while(nowNode!=null) {
			list.add(index, nowNode);
			index++;
			nowNode=nowNode.next;
		}
		int len=list.size();
		for(int i=len-1;i>0;i--) {
			list.get(i).next=list.get(i-1);
		}
		return list.get(len-1);
	}

	public static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\",\"next\":\"" + next + "\"} ";
		}
		
	}
}
